class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int l = 0, r = len - 1, mid;
        //二分
        while(l <= r){
            mid = (l + r) >> 1;
            if(nums[mid] == target) return mid;
            //若是右半边为完全升序子列
            else if(nums[mid] < nums[r]){ 
                if(nums[mid] < target && target <= nums[r]) l = mid + 1;
                //否则，则在左边
                else r = mid - 1; 
                
            } 
            //若是左半边为完全升序子列
            else { 
                //目标值在左边序列
                if(nums[l] <= target && target < nums[mid]) r = mid - 1;
                //否则，则在右边
                else l = mid + 1;
                

            }
        }
        
        return -1;

    }
};